using System;
using System.Collections.Generic;

namespace ParserGenerator.DataStructures
{
    [Serializable]
    public sealed class RedBlackTree<T> where T : IComparable<T>
    {
        public const bool Red = false;
        public const bool Black = true;

        public static bool IsRed(RedBlackTree<T> n) => n != null && n.Color == Red;
        public static bool IsBlack(RedBlackTree<T> n) => !IsRed(n);

        public bool Color { get; private set; }
        public T Value { get; private set; }
        public RedBlackTree<T> Left { get; private set; }
        public RedBlackTree<T> Right { get; private set; }

        private RedBlackTree(T value)
        {
            if (value == null)
                throw new ArgumentNullException(nameof(value));
            Value = value;
        }

        private void FlipColors()
        {
            Color ^= true;
            Left.Color ^= true;
            Right.Color ^= true;
        }

        private RedBlackTree<T> RotateLeft()
        {
            RedBlackTree<T> x = Right;
            Right = x.Left;
            x.Left = this;
            x.Color = Color;
            Color = Red;
            return x;
        }

        private RedBlackTree<T> RotateRight()
        {
            RedBlackTree<T> x = Left;
            Left = x.Right;
            x.Right = this;
            x.Color = Color;
            Color = Red;
            return x;
        }

        private static RedBlackTree<T> Balance(RedBlackTree<T> n)
        {
            if (IsBlack(n.Left) && IsRed(n.Right))
                n = n.RotateLeft();
            if (IsRed(n.Left) && IsRed(n.Left.Left))
                n = n.RotateRight();
            if (IsRed(n.Left) && IsRed(n.Right))
                n.FlipColors();
            return n;
        }

        private static RedBlackTree<T> InsertInto(RedBlackTree<T> n, T value)
        {
            if (n == null)
                return new RedBlackTree<T>(value);
            if (value.CompareTo(n.Value) < 0)
                n.Left = InsertInto(n.Left, value);
            else
                n.Right = InsertInto(n.Right, value);
            return Balance(n);
        }

        public static RedBlackTree<T> Insert(RedBlackTree<T> root, T value)
        {
            if (value == null)
                throw new ArgumentNullException(nameof(value));
            root = InsertInto(root, value);
            root.Color = Black;
            return root;
        }

        private static void CollectInto(RedBlackTree<T> n, List<T> list)
        {
            if (n != null)
            {
                CollectInto(n.Left, list);
                list.Add(n.Value);
                CollectInto(n.Right, list);
            }
        }

        public static List<T> Collect(RedBlackTree<T> root)
        {
            List<T> list = new List<T>();
            CollectInto(root, list);
            return list;
        }
    }
}
